home *** CD-ROM | disk | FTP | other *** search
/ Openstep 4.2 (Developer) / Openstep Developer 4.2.iso / NextDeveloper / Source / GNU / perl / Perl / ext / SDBM_File / sdbm / pair.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-18  |  5.6 KB  |  308 lines
  1. /*
  2.  * sdbm - ndbm work-alike hashed database library
  3.  * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
  4.  * author: oz@nexus.yorku.ca
  5.  * status: public domain.
  6.  *
  7.  * page-level routines
  8.  */
  9.  
  10. #ifndef lint
  11. static char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $";
  12. #endif
  13.  
  14. #include "config.h"
  15. #include "sdbm.h"
  16. #include "tune.h"
  17. #include "pair.h"
  18.  
  19. #define exhash(item)    sdbm_hash((item).dptr, (item).dsize)
  20.  
  21. /* 
  22.  * forward 
  23.  */
  24. static int seepair proto((char *, int, char *, int));
  25.  
  26. /*
  27.  * page format:
  28.  *    +------------------------------+
  29.  * ino    | n | keyoff | datoff | keyoff |
  30.  *     +------------+--------+--------+
  31.  *    | datoff | - - - ---->           |
  32.  *    +--------+---------------------+
  33.  *    |     F R E E A R E A       |
  34.  *    +--------------+---------------+
  35.  *    |  <---- - - - | data          |
  36.  *    +--------+-----+----+----------+
  37.  *    |  key   | data     | key      |
  38.  *    +--------+----------+----------+
  39.  *
  40.  * calculating the offsets for free area:  if the number
  41.  * of entries (ino[0]) is zero, the offset to the END of
  42.  * the free area is the block size. Otherwise, it is the
  43.  * nth (ino[ino[0]]) entry's offset.
  44.  */
  45.  
  46. int
  47. fitpair(pag, need)
  48. char *pag;
  49. int need;
  50. {
  51.     register int n;
  52.     register int off;
  53.     register int free;
  54.     register short *ino = (short *) pag;
  55.  
  56.     off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  57.     free = off - (n + 1) * sizeof(short);
  58.     need += 2 * sizeof(short);
  59.  
  60.     debug(("free %d need %d\n", free, need));
  61.  
  62.     return need <= free;
  63. }
  64.  
  65. void
  66. putpair(pag, key, val)
  67. char *pag;
  68. datum key;
  69. datum val;
  70. {
  71.     register int n;
  72.     register int off;
  73.     register short *ino = (short *) pag;
  74.  
  75.     off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
  76. /*
  77.  * enter the key first
  78.  */
  79.     off -= key.dsize;
  80.     (void) memcpy(pag + off, key.dptr, key.dsize);
  81.     ino[n + 1] = off;
  82. /*
  83.  * now the data
  84.  */
  85.     off -= val.dsize;
  86.     (void) memcpy(pag + off, val.dptr, val.dsize);
  87.     ino[n + 2] = off;
  88. /*
  89.  * adjust item count
  90.  */
  91.     ino[0] += 2;
  92. }
  93.  
  94. datum
  95. getpair(pag, key)
  96. char *pag;
  97. datum key;
  98. {
  99.     register int i;
  100.     register int n;
  101.     datum val;
  102.     register short *ino = (short *) pag;
  103.  
  104.     if ((n = ino[0]) == 0)
  105.         return nullitem;
  106.  
  107.     if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
  108.         return nullitem;
  109.  
  110.     val.dptr = pag + ino[i + 1];
  111.     val.dsize = ino[i] - ino[i + 1];
  112.     return val;
  113. }
  114.  
  115. #ifdef SEEDUPS
  116. int
  117. duppair(pag, key)
  118. char *pag;
  119. datum key;
  120. {
  121.     register short *ino = (short *) pag;
  122.     return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
  123. }
  124. #endif
  125.  
  126. datum
  127. getnkey(pag, num)
  128. char *pag;
  129. int num;
  130. {
  131.     datum key;
  132.     register int off;
  133.     register short *ino = (short *) pag;
  134.  
  135.     num = num * 2 - 1;
  136.     if (ino[0] == 0 || num > ino[0])
  137.         return nullitem;
  138.  
  139.     off = (num > 1) ? ino[num - 1] : PBLKSIZ;
  140.  
  141.     key.dptr = pag + ino[num];
  142.     key.dsize = off - ino[num];
  143.  
  144.     return key;
  145. }
  146.  
  147. int
  148. delpair(pag, key)
  149. char *pag;
  150. datum key;
  151. {
  152.     register int n;
  153.     register int i;
  154.     register short *ino = (short *) pag;
  155.  
  156.     if ((n = ino[0]) == 0)
  157.         return 0;
  158.  
  159.     if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
  160.         return 0;
  161. /*
  162.  * found the key. if it is the last entry
  163.  * [i.e. i == n - 1] we just adjust the entry count.
  164.  * hard case: move all data down onto the deleted pair,
  165.  * shift offsets onto deleted offsets, and adjust them.
  166.  * [note: 0 < i < n]
  167.  */
  168.     if (i < n - 1) {
  169.         register int m;
  170.         register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
  171.         register char *src = pag + ino[i + 1];
  172.         register int   zoo = dst - src;
  173.  
  174.         debug(("free-up %d ", zoo));
  175. /*
  176.  * shift data/keys down
  177.  */
  178.         m = ino[i + 1] - ino[n];
  179. #ifdef DUFF
  180. #define MOVB     *--dst = *--src
  181.  
  182.         if (m > 0) {
  183.             register int loop = (m + 8 - 1) >> 3;
  184.  
  185.             switch (m & (8 - 1)) {
  186.             case 0:    do {
  187.                 MOVB;    case 7:    MOVB;
  188.             case 6:    MOVB;    case 5:    MOVB;
  189.             case 4:    MOVB;    case 3:    MOVB;
  190.             case 2:    MOVB;    case 1:    MOVB;
  191.                 } while (--loop);
  192.             }
  193.         }
  194. #else
  195. #ifdef HAS_MEMMOVE
  196.         dst -= m;
  197.         src -= m;
  198.         memmove(dst, src, m);
  199. #else
  200.         while (m--)
  201.             *--dst = *--src;
  202. #endif
  203. #endif
  204. /*
  205.  * adjust offset index up
  206.  */
  207.         while (i < n - 1) {
  208.             ino[i] = ino[i + 2] + zoo;
  209.             i++;
  210.         }
  211.     }
  212.     ino[0] -= 2;
  213.     return 1;
  214. }
  215.  
  216. /*
  217.  * search for the key in the page.
  218.  * return offset index in the range 0 < i < n.
  219.  * return 0 if not found.
  220.  */
  221. static int
  222. seepair(pag, n, key, siz)
  223. char *pag;
  224. register int n;
  225. register char *key;
  226. register int siz;
  227. {
  228.     register int i;
  229.     register int off = PBLKSIZ;
  230.     register short *ino = (short *) pag;
  231.  
  232.     for (i = 1; i < n; i += 2) {
  233.         if (siz == off - ino[i] &&
  234.             memcmp(key, pag + ino[i], siz) == 0)
  235.             return i;
  236.         off = ino[i + 1];
  237.     }
  238.     return 0;
  239. }
  240.  
  241. void
  242. splpage(pag, new, sbit)
  243. char *pag;
  244. char *new;
  245. long sbit;
  246. {
  247.     datum key;
  248.     datum val;
  249.  
  250.     register int n;
  251.     register int off = PBLKSIZ;
  252.     char cur[PBLKSIZ];
  253.     register short *ino = (short *) cur;
  254.  
  255.     (void) memcpy(cur, pag, PBLKSIZ);
  256.     (void) memset(pag, 0, PBLKSIZ);
  257.     (void) memset(new, 0, PBLKSIZ);
  258.  
  259.     n = ino[0];
  260.     for (ino++; n > 0; ino += 2) {
  261.         key.dptr = cur + ino[0]; 
  262.         key.dsize = off - ino[0];
  263.         val.dptr = cur + ino[1];
  264.         val.dsize = ino[0] - ino[1];
  265. /*
  266.  * select the page pointer (by looking at sbit) and insert
  267.  */
  268.         (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
  269.  
  270.         off = ino[1];
  271.         n -= 2;
  272.     }
  273.  
  274.     debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
  275.            ((short *) new)[0] / 2,
  276.            ((short *) pag)[0] / 2));
  277. }
  278.  
  279. /*
  280.  * check page sanity: 
  281.  * number of entries should be something
  282.  * reasonable, and all offsets in the index should be in order.
  283.  * this could be made more rigorous.
  284.  */
  285. int
  286. chkpage(pag)
  287. char *pag;
  288. {
  289.     register int n;
  290.     register int off;
  291.     register short *ino = (short *) pag;
  292.  
  293.     if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
  294.         return 0;
  295.  
  296.     if (n > 0) {
  297.         off = PBLKSIZ;
  298.         for (ino++; n > 0; ino += 2) {
  299.             if (ino[0] > off || ino[1] > off ||
  300.                 ino[1] > ino[0])
  301.                 return 0;
  302.             off = ino[1];
  303.             n -= 2;
  304.         }
  305.     }
  306.     return 1;
  307. }
  308.